push-재귀-pop-재귀 vs push-재귀-pop

function solution1(n) {
  const answer = [];
  function isSafe(queens,row,col) {
    for(const comp of queens){
      const r = comp[0];
      const c = comp[1];
      if(row===r||col===c|| Math.abs(row-r)===Math.abs(col-c)){ // Math.abs안썼음
        return false;
      }
    }
    return true;
  }

  function solve(queens,row){
    if(row===n){
      answer.push([...queens]); 
      return;
    }

    for(let i=0;i<n;i++){
      const flag = isSafe(queens,row,i);
      if(flag){
        queens.push([row,i]);
        solve(queens,row+1);
        queens.pop();
        //solve(queens.row+1); //이거 넣었으면 안됐음.
      }
    }

  }

  solve([],0);
  console.log(answer);
  return answer.length;
}

// console.log("N-Queens (4):", solution1(4));
console.log("N-Queens (8):", solution1(8));

N-Queen 문제 백트랙킹 문제를 풀다보면 언제는 재귀함수 후에 pop()해서 넣었던걸 뺀 후에 다시 재귀함수를 돌리는 경우가 있고, (ㅔpush-재귀-pop-재귀) 어쩔때는 push-재귀-pop 까지만 한다.

형제 노드 탐색

순열생성과 같이 형제 노드들을 모두 탐색해야 할 때는 push-재귀-pop-재귀. 모든 가능한 경우를 탐색해야할 때.

그런데 내가 위의 N-Queen 문제도 모든 경우를 탐색하는 문제 아닌가?

for문으로 반복을 보장해줬기 때문에 마지막 재귀함수 호출이 없어도 된다.

function solveRecursive(queens, row, col) {
    if (row === n) {
        answer.push([...queens]);
        return;
    }
    if (col >= n) return; 
    
    if (isSafe(queens, row, col)) {
        queens.push([row, col]);        
        solveRecursive(queens, row+1, 0); 
        queens.pop();                   
    }
    
    solveRecursive(queens, row, col+1); 
}

위와 같이 코드를 작성하면 내가 원래 이해하고있던 재귀함수의 형태가 된다.